package com.dmall.graph.floodfill;

/**
 * @author: xiao1.wang
 * @date: 2022/6/19 21:04
 */
public class Solution695 {

    private boolean[][] visited;
    private int R, C;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private int[][] grid;

    private int max = 0;

    public int maxAreaOfIsland(int[][] grid) {
        this.grid = grid;
        this.R = grid.length;
        this.C = grid[0].length;
        this.visited = new boolean[R][C];

        for (int r = 0; r < this.R; r++) {
            for (int c = 0; c < this.C; c++) {
                if (!visited[r][c] && grid[r][c] == 1) {
                    max = Math.max(max, dfs(r, c));
                }
            }
        }
        return max;
    }

    private int dfs(int r, int c) {
        visited[r][c] = true;
        int res = 1;
        for (int d = 0; d < 4; d++) {
            int nextr = r + dirs[d][0];
            int nextc = c + dirs[d][1];
            if (inArea(nextr, nextc) && !visited[nextr][nextc] && grid[nextr][nextc] == 1) {
                res += dfs(nextr, nextc);
            }
        }
        return res;
    }

    private boolean inArea(int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C;
    }

    public static void main(String[] args) {
        int[][] grid = {
                {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
                {0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
                {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}
        };
        Solution695 solution695 = new Solution695();
        System.out.println(solution695.maxAreaOfIsland(grid));
    }
}
